package com.mrzhou.study.struct.recursion;

/**
 * 八皇后问题代码实现:
 *  这里写一点个人对递归的理解:
 *      递归的特性: 在每次调用时都会创建一个内存保存当前方法的变量, 整体上递归的内容是一个栈
 *      所以八皇后问题是利用递归的特性, 每次调用都创建一个内存空间保存, 当到达边界时依次执行栈中全部的指令
 *      所以八皇后摆放的n必须作为一个变量传入, 只有这样才会在每次调用时将n作为变量保存到栈空间,
 *      如果n作为全局变量则不会复制
 */
public class EightQueens {

    int[] queens = new int[8];
    int count;  // 总共解法
    int executeCount; // 放置的次数

    public static void main(String[] args) {
        EightQueens queens = new EightQueens();
        queens.place();
        System.out.printf("解法有: %d\n", queens.count);
        System.out.printf("摆放次数共: %d\n", queens.executeCount);
    }

    public void place() {
        place(0);
    }

    private void place(int n) {
        if(n == queens.length) {
            show();
            return;
        }

        for(int i = 0; i < queens.length; i++) { // i表示放置的位置下标
            queens[n] = i;
            if(isPlace(n)) { // 判断当前的位置是否可以放置
                place(n + 1);
            }
        }
    }

    public boolean isPlace(int n) {
        executeCount++; // 统计放置次数

        for(int i = 0; i < n; i++) {
            //  n =1, i = 0
            if(queens[i] == queens[n]|| Math.abs(n-i) == Math.abs(queens[n] - queens[i])) {
                return false;
            }
        }
        return true;
    }

    public void show() {
        count++;
        for (int i = 0; i < queens.length; i++) {
            System.out.print(queens[i] + ", ");
        }
        System.out.println();
    }

}
